home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / triv_lib / mrchcube.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-12-31  |  18.4 KB  |  510 lines
  1. /******************************************************************************
  2. * An implementation of the marching cube algorithm.                  *
  3. *                                          *
  4. *                        Gershon Elber, Dec 1992.      *
  5. ******************************************************************************/
  6.  
  7. #include <stdio.h>
  8. #include "irit_sm.h"
  9. #include "mrchcube.h"
  10.  
  11. #define MARCH_CUBE_EPS    1e-8
  12.  
  13. static int MCComputeEdgeInter(MCCubeCornerScalarStruct *CCS,
  14.                   RealType Threshold,
  15.                   int VrtxIndex1,
  16.                   int VrtxIndex2,
  17.                   PointType Pos,
  18.                   PointType Nrml);
  19. static void MCAppendEList(MCEdgeStruct *NewEdges, MCEdgeStruct **EdgeList);
  20. static MCEdgeStruct *MCGetEdgesFromFace(MCCubeCornerScalarStruct *CCS,
  21.                     int InterEdgeIndex1,
  22.                     int InterEdgeIndex2,
  23.                     int InterEdgeIndex3,
  24.                     int InterEdgeIndex4);
  25. static void MCPurgeZeroLenEdges(MCEdgeStruct **AllEList);
  26.  
  27. /*****************************************************************************
  28. * DESCRIPTION:                                                               M
  29. * Given 8 cube corner values (scalars), compute the polygon(s) in this cube  M
  30. * along the isosurface at Threshold. if CCS has gradient information, it is  M
  31. * used to approximate normals at the vertices.                     M
  32. *                                                                            M
  33. *                                                                            M
  34. *                                                                            V
  35. *                     7            K           6                             V
  36. *                      ***********************                               V
  37. *                    * +                   * *                               V
  38. *                L *   +                 *   *              Vertices 0 - 7   V
  39. *                *     +     I         * J   *              Edges    A - L   V
  40. *            4 *********************** 5     *                               V
  41. *              *       +             *       *                               V
  42. *              *       +             *       * G                             V
  43. *              *       + H           *       *                               V
  44. *              *       +             *       *                               V
  45. *              *       +             * F     *                               V
  46. *            E *       +       C     *       *                               V
  47. *              *       ++++++++++++++*+++++++* 2                             V
  48. *              *   D + 3             *     *                                 V
  49. *              *   +                 *   * B                                 V
  50. *              * +                   * *                                     V
  51. *              ***********************                                       V
  52. *             0           A           1                                      V
  53. *                                                                            *
  54. * PARAMETERS:                                                                M
  55. *   CCS:          The cube's dimensions/information.                         M
  56. *   Threshold:    Iso surface level.                                         M
  57. *                                                                            *
  58. * RETURN VALUE:                                                              M
  59. *   MCPolygonStruct *:   List of polygons (not necessarily triangles), or    M
  60. *                        possibly NULL.                                      M
  61. *                                                                            *
  62. * KEYWORDS:                                                                  M
  63. *   MCThresholdCube, marching cubes                                          M
  64. *****************************************************************************/
  65. MCPolygonStruct *MCThresholdCube(MCCubeCornerScalarStruct *CCS,
  66.                  RealType Threshold)
  67. {
  68.     MCEdgeStruct
  69.     *AllEList = NULL;
  70.     MCPolygonStruct
  71.     *AllPList = NULL;
  72.  
  73.     /* Computes the position of the 8 _Vertices. */
  74.     MC_COMP_V_POS(0.0,               0.0,               0.0,
  75.           MC_VRTX_0);
  76.     MC_COMP_V_POS(CCS -> CubeDim[0], 0.0,               0.0,
  77.           MC_VRTX_1);
  78.     MC_COMP_V_POS(CCS -> CubeDim[0], CCS -> CubeDim[1], 0.0,
  79.           MC_VRTX_2);
  80.     MC_COMP_V_POS(0.0,               CCS -> CubeDim[1], 0.0,
  81.           MC_VRTX_3);
  82.  
  83.     MC_COMP_V_POS(0.0,               0.0,               CCS -> CubeDim[2],
  84.           MC_VRTX_4);
  85.     MC_COMP_V_POS(CCS -> CubeDim[0], 0.0,               CCS -> CubeDim[2],
  86.           MC_VRTX_5);
  87.     MC_COMP_V_POS(CCS -> CubeDim[0], CCS -> CubeDim[1], CCS -> CubeDim[2],
  88.           MC_VRTX_6);
  89.     MC_COMP_V_POS(0.0,               CCS -> CubeDim[1], CCS -> CubeDim[2],
  90.           MC_VRTX_7);
  91.  
  92.     /* Test and compute any edge that intersect the Threshold value. */
  93.     CCS -> _Intersect = FALSE;
  94.     CCS -> _InterHighV[MC_EDGE_A] =
  95.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_0, MC_VRTX_1,
  96.                CCS -> _InterPos[MC_EDGE_A],
  97.                CCS -> _InterNrml[MC_EDGE_A]);
  98.     CCS -> _InterHighV[MC_EDGE_B] =
  99.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_1, MC_VRTX_2,
  100.                CCS -> _InterPos[MC_EDGE_B],
  101.                CCS -> _InterNrml[MC_EDGE_B]);
  102.     CCS -> _InterHighV[MC_EDGE_C] =
  103.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_2, MC_VRTX_3,
  104.                CCS -> _InterPos[MC_EDGE_C],
  105.                CCS -> _InterNrml[MC_EDGE_C]);
  106.     CCS -> _InterHighV[MC_EDGE_D] =
  107.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_3, MC_VRTX_0,
  108.                CCS -> _InterPos[MC_EDGE_D],
  109.                CCS -> _InterNrml[MC_EDGE_D]);
  110.     CCS -> _InterHighV[MC_EDGE_E] =
  111.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_0, MC_VRTX_4,
  112.                CCS -> _InterPos[MC_EDGE_E],
  113.                CCS -> _InterNrml[MC_EDGE_E]);
  114.     CCS -> _InterHighV[MC_EDGE_F] =
  115.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_1, MC_VRTX_5,
  116.                CCS -> _InterPos[MC_EDGE_F],
  117.                CCS -> _InterNrml[MC_EDGE_F]);
  118.     CCS -> _InterHighV[MC_EDGE_G] =
  119.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_2, MC_VRTX_6,
  120.                CCS -> _InterPos[MC_EDGE_G],
  121.                CCS -> _InterNrml[MC_EDGE_G]);
  122.     CCS -> _InterHighV[MC_EDGE_H] =
  123.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_3, MC_VRTX_7,
  124.                CCS -> _InterPos[MC_EDGE_H],
  125.                CCS -> _InterNrml[MC_EDGE_H]);
  126.     CCS -> _InterHighV[MC_EDGE_I] =
  127.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_4, MC_VRTX_5,
  128.                CCS -> _InterPos[MC_EDGE_I],
  129.                CCS -> _InterNrml[MC_EDGE_I]);
  130.     CCS -> _InterHighV[MC_EDGE_J] =
  131.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_5, MC_VRTX_6,
  132.                CCS -> _InterPos[MC_EDGE_J],
  133.                CCS -> _InterNrml[MC_EDGE_J]);
  134.     CCS -> _InterHighV[MC_EDGE_K] =
  135.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_6, MC_VRTX_7,
  136.                CCS -> _InterPos[MC_EDGE_K],
  137.                CCS -> _InterNrml[MC_EDGE_K]);
  138.     CCS -> _InterHighV[MC_EDGE_L] =
  139.     MCComputeEdgeInter(CCS, Threshold, MC_VRTX_4, MC_VRTX_7,
  140.                CCS -> _InterPos[MC_EDGE_L],
  141.                CCS -> _InterNrml[MC_EDGE_L]);
  142.     if (!CCS->_Intersect)
  143.     return NULL;
  144.  
  145.     /* For each of the six faces, compute polygon interior edges for that   */
  146.     /* face and save all of them into a global list.                 */
  147.     MCAppendEList(MCGetEdgesFromFace(CCS, MC_EDGE_D, MC_EDGE_C,
  148.                           MC_EDGE_B, MC_EDGE_A), &AllEList);
  149.     MCAppendEList(MCGetEdgesFromFace(CCS, MC_EDGE_A, MC_EDGE_F,
  150.                           MC_EDGE_I, MC_EDGE_E), &AllEList);
  151.     MCAppendEList(MCGetEdgesFromFace(CCS, MC_EDGE_B, MC_EDGE_G,
  152.                           MC_EDGE_J, MC_EDGE_F), &AllEList);
  153.     MCAppendEList(MCGetEdgesFromFace(CCS, MC_EDGE_C, MC_EDGE_H,
  154.                           MC_EDGE_K, MC_EDGE_G), &AllEList);
  155.     MCAppendEList(MCGetEdgesFromFace(CCS, MC_EDGE_D, MC_EDGE_E,
  156.                           MC_EDGE_L, MC_EDGE_H), &AllEList);
  157.     MCAppendEList(MCGetEdgesFromFace(CCS, MC_EDGE_I, MC_EDGE_J,
  158.                           MC_EDGE_K, MC_EDGE_L), &AllEList);
  159.  
  160.     MCPurgeZeroLenEdges(&AllEList);
  161.  
  162. #ifdef DEBUG_PRINT_EDGES
  163.     {
  164.     MCEdgeStruct
  165.         *E = AllEList;
  166.     
  167.     fprintf(stderr, "\nCube edges [%lf %lf %lf] [%lf %lf %lf]:\n",
  168.         CCS -> Vrtx0Lctn[0], CCS -> Vrtx0Lctn[1], CCS -> Vrtx0Lctn[2],
  169.         CCS -> CubeDim[0], CCS -> CubeDim[1], CCS -> CubeDim[2]);
  170.     for (; E != NULL; E = E -> Pnext) {
  171.         fprintf(stderr,
  172.             "Edge = %10.6lg, %10.6lg, %10.6lg,    %10.6lg, %10.6lg, %10.6lg\n",
  173.             E -> V[0][0], E -> V[0][1], E -> V[0][2],
  174.             E -> V[1][0], E -> V[1][1], E -> V[1][2]);            
  175.     }
  176.     }
  177. #endif /* DEBUG_PRINT_EDGES */
  178.  
  179.     /* Merge the Vertices into polygons. */
  180.     while (AllEList != NULL) {
  181.     int NumOfVertices = 2;
  182.     CagdBType
  183.         ClosedPoly = FALSE;
  184.     MCPolygonStruct
  185.         *P = (MCPolygonStruct *) IritMalloc(sizeof(MCPolygonStruct));
  186.     MCEdgeStruct *E2, *E2Prev,
  187.         *E = AllEList;
  188.  
  189.     PT_COPY(P -> V[0], E -> V[0]);
  190.     PT_COPY(P -> N[0], E -> N[0]);
  191.     PT_COPY(P -> V[1], E -> V[1]);
  192.     PT_COPY(P -> N[1], E -> N[1]);
  193.  
  194.     AllEList = AllEList -> Pnext;
  195.     E -> Pnext = NULL;
  196.     IritFree((VoidPtr) E);
  197.  
  198.     while (!ClosedPoly) {
  199.         if (AllEList == NULL) {
  200.         TRIV_FATAL_ERROR(TRIV_ERR_NO_CLOSED_POLYGON);
  201.         return NULL;
  202.         }
  203.  
  204.         for (E2 = E2Prev = AllEList; E2 != NULL;) {
  205.         CagdBType
  206.             FoundMatch = FALSE;
  207.  
  208.         if (PT_APX_EQ_EPS(P -> V[NumOfVertices - 1], E2 -> V[1],
  209.                   MARCH_CUBE_EPS)) {
  210.             PT_COPY(P -> V[NumOfVertices], E2 -> V[0]);
  211.             PT_COPY(P -> N[NumOfVertices], E2 -> N[0]);
  212.             NumOfVertices++;
  213.             FoundMatch = TRUE;
  214.         }
  215.         else if (PT_APX_EQ_EPS(P -> V[NumOfVertices - 1],
  216.                        E2 -> V[0], MARCH_CUBE_EPS)) {
  217.             PT_COPY(P -> V[NumOfVertices], E2 -> V[1]);
  218.             PT_COPY(P -> N[NumOfVertices], E2 -> N[1]);
  219.             NumOfVertices++;
  220.             FoundMatch = TRUE;
  221.         }
  222.  
  223.         if (FoundMatch) {
  224.             if (E2 == AllEList) {
  225.             AllEList = AllEList -> Pnext;
  226.             }
  227.             else {
  228.             E2Prev -> Pnext = E2 -> Pnext;
  229.             }
  230.             IritFree((VoidPtr) E2);
  231.             E2 = E2Prev = AllEList;
  232.         }
  233.         else {
  234.             E2Prev = E2;
  235.             E2 = E2 -> Pnext;
  236.         }
  237.  
  238.         if (PT_APX_EQ_EPS(P -> V[0], P -> V[NumOfVertices - 1],
  239.                   MARCH_CUBE_EPS)) {
  240.             P -> NumOfVertices = NumOfVertices;
  241.             P -> Pnext = AllPList;
  242.             AllPList = P;
  243.             ClosedPoly = TRUE;
  244.             break;
  245.         }
  246.         }
  247.     }
  248.     }
  249.  
  250.     return AllPList;
  251. }
  252.  
  253. /*****************************************************************************
  254. * DESCRIPTION:                                                               *
  255. * Drop zero length edges.                             *
  256. *                                                                            *
  257. * PARAMETERS:                                                                *
  258. *   AllEList:  To clean up.                                                  *
  259. *                                                                            *
  260. * RETURN VALUE:                                                              *
  261. *   void                                                                     *
  262. *****************************************************************************/
  263. static void MCPurgeZeroLenEdges(MCEdgeStruct **AllEList)
  264. {
  265.     MCEdgeStruct
  266.     *E = *AllEList,
  267.     *PrevE = E;
  268.  
  269.     while (E != NULL) {
  270.     PointType Pt;
  271.  
  272.     PT_SUB(Pt, E -> V[0], E -> V[1]);
  273.  
  274.     if (PT_LENGTH(Pt) < MARCH_CUBE_EPS) {
  275.         if (E == *AllEList) {
  276.         *AllEList = E -> Pnext;
  277.         IritFree((VoidPtr) E);
  278.         E = PrevE = *AllEList;
  279.         }
  280.         else {
  281.         PrevE -> Pnext = E -> Pnext;
  282.         IritFree((VoidPtr) E);
  283.         E = PrevE -> Pnext;
  284.         }
  285.     }
  286.     else {
  287.         PrevE = E;
  288.         E = E -> Pnext;
  289.     }
  290.     }
  291. }
  292.  
  293. /*****************************************************************************
  294. * DESCRIPTION:                                                               *
  295. * Computes the intersection of a cube edge with the scalar threshold level,  *
  296. * given the edge two indices.                             *
  297. *   Sets CCS _Intersect if found intersection.                     *
  298. *   Updates the Pos parameter to the intersection position or set it to      *
  299. * INFINITY if no Intersection is found.                         *
  300. *   Returns the Index of the vertex with value ABOVE the Threshold level or  *
  301. * MC_VRTX_NONE of no intersection.                         *
  302. *                                                                            *
  303. * PARAMETERS:                                                                *
  304. *   CCS:           Cube to consider.                         *
  305. *   Threshold:     Iso surface level.                         *
  306. *   VrtxIndex1, VrtxIndex2:    Two vertices of intersecting edge.            *
  307. *   Pos:           Where position is to be saved.                            *
  308. *   Nrml:          Where Normal at position is to be saved.                  *
  309. *                                                                            *
  310. * RETURN VALUE:                                                              *
  311. *   int:           Index of edge's vertex above Threshold, or MC_VRTX_NONE   *
  312. *                  if no intersection.                                       *
  313. *****************************************************************************/
  314. static int MCComputeEdgeInter(MCCubeCornerScalarStruct *CCS,
  315.                   RealType Threshold,
  316.                   int VrtxIndex1,
  317.                   int VrtxIndex2,
  318.                   PointType Pos,
  319.                   PointType Nrml)
  320. {
  321.     int i;
  322.     RealType t,
  323.     Val1 = CCS -> Corners[VrtxIndex1],
  324.     Val2 = CCS -> Corners[VrtxIndex2],
  325.     MaxVal = MAX(Val1, Val2),
  326.     MinVal = MIN(Val1, Val2);
  327.  
  328.     if (MinVal >= Threshold || MaxVal < Threshold) {
  329.     Pos[0] = Pos[1] = Pos[2] = INFINITY;
  330.     return MC_VRTX_NONE;
  331.     }
  332.  
  333.     t = (Val1 - Threshold) / (Val1 - Val2);
  334.  
  335.     for (i = 0; i < 3; i++)
  336.     Pos[i] = CCS -> _VrtxPos[VrtxIndex2][i] * t +
  337.              CCS -> _VrtxPos[VrtxIndex1][i] * (1 - t);
  338.  
  339.     if (CCS -> HasGradient) {
  340.     Nrml[0] = CCS -> GradientX[VrtxIndex2] * t +
  341.           CCS -> GradientX[VrtxIndex1] * (1 - t);
  342.     Nrml[1] = CCS -> GradientY[VrtxIndex2] * t +
  343.           CCS -> GradientY[VrtxIndex1] * (1 - t);
  344.     Nrml[2] = CCS -> GradientZ[VrtxIndex2] * t +
  345.           CCS -> GradientZ[VrtxIndex1] * (1 - t);
  346.     PT_NORMALIZE(Nrml);
  347.     }
  348.     else {
  349.     Nrml[0] = Nrml[1] = Nrml[2] = 0.0;
  350.     }
  351.  
  352.     CCS -> _Intersect = TRUE;
  353.  
  354.     return Val1 > Val2 ? VrtxIndex1 : VrtxIndex2;
  355. }
  356.  
  357. /*****************************************************************************
  358. * DESCRIPTION:                                                               *
  359. * Appends NewEdges to EdgeList                             *
  360. *                                                                            *
  361. * PARAMETERS:                                                                *
  362. *   NewEdges:   Edges to append to EdgeList.                                 *
  363. *   EdgeList:   Exists edge list to append NewEdges to.                      *
  364. *                                                                            *
  365. * RETURN VALUE:                                                              *
  366. *   void                                                                     *
  367. *****************************************************************************/
  368. static void MCAppendEList(MCEdgeStruct *NewEdges, MCEdgeStruct **EdgeList)
  369. {
  370.     MCEdgeStruct
  371.     *E = NewEdges;
  372.  
  373.     if (E != NULL) {
  374.     while (E -> Pnext != NULL)
  375.         E = E -> Pnext;
  376.     E -> Pnext = *EdgeList;
  377.     *EdgeList = NewEdges;
  378.     }
  379. }
  380.  
  381. /*****************************************************************************
  382. * DESCRIPTION:                                                               *
  383. * Extract intersection edges from a given face (if any).             *
  384. *                                                                            *
  385. * PARAMETERS:                                                                *
  386. *   CCS:                     One voxel to consider.                          *
  387. *   InterEdgeIndex1/2/3/4:   Four indices of face.                           *
  388. *                                                                            *
  389. * RETURN VALUE:                                                              *
  390. *   MCEdgeStruct *:          List of edges of iso surface intersecting face. *
  391. *****************************************************************************/
  392. static MCEdgeStruct *MCGetEdgesFromFace(MCCubeCornerScalarStruct *CCS,
  393.                     int InterEdgeIndex1,
  394.                     int InterEdgeIndex2,
  395.                     int InterEdgeIndex3,
  396.                     int InterEdgeIndex4)
  397. {
  398.     CagdBType
  399.     Inter1 = CCS -> _InterPos[InterEdgeIndex1][0] != INFINITY,
  400.     Inter2 = CCS -> _InterPos[InterEdgeIndex2][0] != INFINITY,
  401.     Inter3 = CCS -> _InterPos[InterEdgeIndex3][0] != INFINITY,
  402.     Inter4 = CCS -> _InterPos[InterEdgeIndex4][0] != INFINITY;
  403.     int i, j,
  404.     NumOfInters = Inter1 + Inter2 + Inter3 + Inter4;
  405.  
  406.     /* We can have either two or four intersections. */
  407.     if (NumOfInters == 0) {
  408.     return NULL;
  409.     }
  410.     else if (NumOfInters == 2) {
  411.     int NumOfVertices = 0;
  412.     struct MCEdgeStruct
  413.         *Edge = (MCEdgeStruct *) IritMalloc(sizeof(MCEdgeStruct));
  414.  
  415.     /* Make an edge from one intersection to the next. */
  416.     if (Inter1) {
  417.         PT_COPY(Edge -> V[NumOfVertices],
  418.             CCS -> _InterPos[InterEdgeIndex1]);
  419.         PT_COPY(Edge -> N[NumOfVertices],
  420.             CCS -> _InterNrml[InterEdgeIndex1]);
  421.         NumOfVertices++;
  422.     }
  423.     if (Inter2) {
  424.         PT_COPY(Edge -> V[NumOfVertices],
  425.             CCS -> _InterPos[InterEdgeIndex2]);
  426.         PT_COPY(Edge -> N[NumOfVertices],
  427.             CCS -> _InterNrml[InterEdgeIndex2]);
  428.         NumOfVertices++;
  429.     }
  430.     if (Inter3) {
  431.         PT_COPY(Edge -> V[NumOfVertices],
  432.             CCS -> _InterPos[InterEdgeIndex3]);
  433.         PT_COPY(Edge -> N[NumOfVertices],
  434.             CCS -> _InterNrml[InterEdgeIndex3]);
  435.         NumOfVertices++;
  436.     }
  437.     if (Inter4) {
  438.         PT_COPY(Edge -> V[NumOfVertices],
  439.             CCS -> _InterPos[InterEdgeIndex4]);
  440.         PT_COPY(Edge -> N[NumOfVertices],
  441.             CCS -> _InterNrml[InterEdgeIndex4]);
  442.         NumOfVertices++;
  443.     }
  444.     if (NumOfVertices != 2) {
  445.         TRIV_FATAL_ERROR(TRIV_ERR_TWO_INTERSECTIONS);
  446.         return NULL;
  447.     }
  448.  
  449.     Edge -> Pnext = NULL;
  450.  
  451.     return Edge;
  452.     }
  453.     else if (NumOfInters == 4) {
  454.     int Indirect[4];
  455.     CagdBType Found;
  456.     struct MCEdgeStruct
  457.         *Edge1 = (MCEdgeStruct *) IritMalloc(sizeof(MCEdgeStruct)),
  458.         *Edge2 = (MCEdgeStruct *) IritMalloc(sizeof(MCEdgeStruct));
  459.  
  460.     Indirect[0] = InterEdgeIndex1;
  461.     Indirect[1] = InterEdgeIndex2;
  462.     Indirect[2] = InterEdgeIndex3;
  463.     Indirect[3] = InterEdgeIndex4;
  464.  
  465.     /* Use the _InterHighV To make a decision. */
  466.  
  467.     /* Find first pair. */
  468.     for (i = 0, Found = FALSE; i < 3 && !Found; i++) {
  469.         for (j = i + 1; j < 4 && !Found; j++) {
  470.         if (CCS -> _InterHighV[Indirect[i]] ==
  471.             CCS -> _InterHighV[Indirect[j]]) 
  472.             Found = TRUE;
  473.         }
  474.     }
  475.     if (Found) {
  476.         i--;
  477.         j--;
  478.     }
  479.     else {
  480.         TRIV_FATAL_ERROR(TRIV_ERR_NO_MATCH_PAIR);
  481.         return NULL;
  482.     }
  483.  
  484.     PT_COPY(Edge1 -> V[0], CCS -> _InterPos[Indirect[i]]);
  485.     PT_COPY(Edge1 -> N[0], CCS -> _InterNrml[Indirect[i]]);
  486.     PT_COPY(Edge1 -> V[1], CCS -> _InterPos[Indirect[j]]);
  487.     PT_COPY(Edge1 -> N[1], CCS -> _InterNrml[Indirect[j]]);
  488.     Indirect[i] = MC_EDGE_NONE;
  489.     Indirect[j] = MC_EDGE_NONE;
  490.  
  491.     /* Find second pair. */
  492.     for (i = j = 0; i < 4; i++) {
  493.         if (Indirect[i] != MC_EDGE_NONE) {
  494.         PT_COPY(Edge2 -> V[j], CCS -> _InterPos[Indirect[i]]);
  495.         PT_COPY(Edge2 -> N[j], CCS -> _InterNrml[Indirect[i]]);
  496.         j++;
  497.         }
  498.     }
  499.  
  500.     Edge1 -> Pnext = Edge2;
  501.     Edge2 -> Pnext = NULL;
  502.  
  503.     return Edge1;
  504.     }
  505.     else {
  506.     TRIV_FATAL_ERROR(TRIV_ERR_2_OR_4_INTERS);
  507.     return NULL;
  508.     }
  509. }
  510.